{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pour Water"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pourWater"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #倒水"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出一个地形高度图， <code>heights[i]</code> 表示该索引处的高度。每个索引的宽度为 1。在 <code>V</code> 个单位的水落在索引 <code>K</code> 处以后，每个索引位置有多少水？</p>\n",
    "\n",
    "<p>水最先会在索引 <code>K</code> 处下降并且落在该索引位置的最高地形或水面之上。然后按如下方式流动：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果液滴最终可以通过向左流动而下降，则向左流动。</li>\n",
    "\t<li>否则，如果液滴最终可以通过向右流动而下降，则向右流动。</li>\n",
    "\t<li>否则，在当前的位置上升。</li>\n",
    "\t<li>这里，“最终下降” 的意思是液滴如果按此方向移动的话，最终可以下降到一个较低的水平。而且，“水平”的意思是当前列的地形的高度加上水的高度。</li>\n",
    "</ul>\n",
    "\n",
    "<p>我们可以假定在数组两侧的边界外有无限高的地形。而且，不能有部分水在多于 1 个的网格块上均匀分布 - 每个单位的水必须要位于一个块中。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [2,1,1,2,1,2,2], V = 4, K = 3\n",
    "<strong>输出：</strong>[2,2,2,3,2,2,2]\n",
    "<strong>解释：</strong>\n",
    "#       #\n",
    "#       #\n",
    "##  # ###\n",
    "#########\n",
    " 0123456    <- 索引\n",
    "\n",
    "第一个水滴降落在索引 K = 3 上：\n",
    "\n",
    "#       #\n",
    "#   w   #\n",
    "##  # ###\n",
    "#########\n",
    " 0123456    \n",
    "\n",
    "当向左或向右移动时，水可以移动到相同或更低的高度。When moving left or right, the water can only move to the same level or a lower level.\n",
    "（从水平上看，意思是该列的地形高度加上水的高度）\n",
    "由于向左移动可以最终下落，因此向左移动。\n",
    "（一个水滴 “下落” 的意思是可以相比之前可以进入更低的高度）\n",
    "\n",
    "#       #\n",
    "#       #\n",
    "## w# ###\n",
    "#########\n",
    " 0123456    \n",
    "\n",
    "由于向左移动不会使其降落，所以停在该位置上。下一个水滴下落：\n",
    "\n",
    "#       #\n",
    "#   w   #\n",
    "## w# ###\n",
    "#########\n",
    " 0123456  \n",
    "\n",
    "\n",
    "由于新水滴向左移动可以最终下落，因此向左移动。\n",
    "注意水滴仍然是优先选择向左移动，\n",
    "尽管可以向右移动（而且向右移动可以下落更快）\n",
    "\n",
    "\n",
    "#       #\n",
    "#  w    #\n",
    "## w# ###\n",
    "#########\n",
    " 0123456  \n",
    "\n",
    "#       #\n",
    "#       #\n",
    "##ww# ###\n",
    "#########\n",
    " 0123456  \n",
    "\n",
    "经过刚才的阶段后，第三个水滴下落。\n",
    "由于向左移动不会最终下落，因此尝试向右移动。\n",
    "由于向右移动可以最终下落，因此向右移动。\n",
    "\n",
    "\n",
    "#       #\n",
    "#   w   #\n",
    "##ww# ###\n",
    "#########\n",
    " 0123456  \n",
    "\n",
    "#       #\n",
    "#       #\n",
    "##ww#w###\n",
    "#########\n",
    " 0123456  \n",
    "\n",
    "最终，第四个水滴下落。\n",
    "由于向左移动不会最终下落，因此尝试向右移动。\n",
    "由于向右移动不会最终下落，因此停在当前位置：\n",
    "\n",
    "#       #\n",
    "#   w   #\n",
    "##ww#w###\n",
    "#########\n",
    " 0123456  \n",
    "\n",
    "最终的答案为 [2,2,2,3,2,2,2]:\n",
    "\n",
    "    #    \n",
    " ####### \n",
    " ####### \n",
    " 0123456 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [1,2,3,4], V = 2, K = 2\n",
    "<strong>输出：</strong>[2,3,3,4]\n",
    "<strong>解释：</strong>\n",
    "最后的水滴落在索引 1 位置，因为继续向左移动不会使其下降到更低的高度。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [3,1,3], V = 5, K = 1\n",
    "<strong>输出：</strong>[4,4,4]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>注：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>heights</code> 的长度为 <code>[1, 100]</code> ，并且每个数的范围为<code>[0, 99]</code>。</li>\n",
    "\t<li><code>V</code> 的范围 <code>[0, 2000]</code>。</li>\n",
    "\t<li><code>K</code> 的范围 <code>[0, heights.length - 1]</code>。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pour-water](https://leetcode.cn/problems/pour-water/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pour-water](https://leetcode.cn/problems/pour-water/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,1,2,1,2,2]\\n4\\n3', '[1,2,3,4]\\n2\\n2', '[3,1,3]\\n5\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, h: List[int], v: int, k: int) -> List[int]:\n",
    "        n = len(h)\n",
    "        while v:\n",
    "            st = k\n",
    "            while st > 0 and h[st-1] <= h[st]:\n",
    "                st -= 1\n",
    "            # 如果这个最后的停留点和上一个点的位置是一样的 就右边移动 表示往左已经不能使得水滴落下了\n",
    "            while st < k and h[st] == h[st+1]:\n",
    "                st += 1\n",
    "            while st + 1 < n and h[st] >= h[st+1]:\n",
    "                st += 1\n",
    "            while st > k and h[st-1] == h[st]:\n",
    "                st -= 1\n",
    "            h[st] += 1\n",
    "            v -= 1\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:\n",
    "        for _ in range(volume):\n",
    "            flag = True\n",
    "            left,pre = k - 1,k\n",
    "            while left >= 0 and heights[left] <= heights[pre]:\n",
    "                if heights[left] < heights[pre]:\n",
    "                    pre = left\n",
    "                left -= 1\n",
    "            if pre < k:\n",
    "                heights[pre] += 1\n",
    "                flag = False\n",
    "            else:\n",
    "                right,pre = k + 1,k\n",
    "                while right < len(heights) and heights[right] <= heights[pre]:\n",
    "                    if heights[right] < heights[pre]:\n",
    "                        pre = right\n",
    "                    right += 1\n",
    "                if pre > k:\n",
    "                    heights[pre] += 1\n",
    "                    flag = False\n",
    "            if flag:\n",
    "                heights[k] += 1\n",
    "        return heights\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, heights: List[int], V: int, k: int) -> List[int]:\n",
    "        n=len(heights)\n",
    "        for _ in range(V):\n",
    "            cur=k\n",
    "            best=k\n",
    "            #先左后右\n",
    "            while cur>0 and heights[cur]>=heights[cur-1]:\n",
    "                if heights[cur-1]<heights[cur]:\n",
    "                    best=cur-1\n",
    "                cur-=1\n",
    "            if best!=k:\n",
    "                heights[best]+=1\n",
    "                continue\n",
    "            while cur+1<n and heights[cur]>=heights[cur+1]:\n",
    "                if heights[cur+1]<heights[cur]:\n",
    "                    best=cur+1\n",
    "                cur+=1\n",
    "            if best!=k:\n",
    "                heights[best]+=1\n",
    "                continue\n",
    "            heights[k]+=1\n",
    "        return heights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:\n",
    "        # 核心思想：模拟\n",
    "        n = len(heights)\n",
    "        for _ in range(volume):\n",
    "            for d in (-1,1):\n",
    "                i = min_v = k\n",
    "                # 如果当前方向的值，小于等于右边的值，就一直往当前方向前进\n",
    "                while 0 <= i+d < n and heights[i+d] <= heights[i]:\n",
    "                    if heights[i+d] < heights[i]:\n",
    "                        min_v = i+d\n",
    "                    i += d\n",
    "                if min_v != k:\n",
    "                    heights[min_v] += 1\n",
    "                    break\n",
    "            else:\n",
    "                heights[k] += 1\n",
    "        return heights\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:\n",
    "        for _ in range(volume):\n",
    "            pos = k\n",
    "\n",
    "            while pos > 0 and heights[pos] >= heights[pos - 1]:\n",
    "                pos -= 1\n",
    "            \n",
    "            while pos < len(heights) - 1 and heights[pos] >= heights[pos + 1]:\n",
    "                pos += 1\n",
    "            \n",
    "            while pos > k and heights[pos] == heights[pos - 1]:\n",
    "                pos -= 1\n",
    "            \n",
    "            heights[pos] += 1\n",
    "        return heights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, heights: List[int], V: int, k: int) -> List[int]:\n",
    "        n=len(heights)\n",
    "        for _ in range(V):\n",
    "            cur=k\n",
    "            best=k\n",
    "            #先左后右\n",
    "            while cur>0 and heights[cur]>=heights[cur-1]:\n",
    "                if heights[cur-1]<heights[cur]:\n",
    "                    best=cur-1\n",
    "                cur-=1\n",
    "            if best!=k:\n",
    "                heights[best]+=1\n",
    "                continue\n",
    "            while cur+1<n and heights[cur]>=heights[cur+1]:\n",
    "                if heights[cur+1]<heights[cur]:\n",
    "                    best=cur+1\n",
    "                cur+=1\n",
    "            if best!=k:\n",
    "                heights[best]+=1\n",
    "                continue\n",
    "            heights[k]+=1\n",
    "        return heights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:\n",
    "        # 枚举每滴水的流向位置\n",
    "        for _ in range(volume):\n",
    "            # 先向左再向右边\n",
    "            for d in (-1,1):\n",
    "                i = best = k\n",
    "                while 0 <= i+d < len(heights) and heights[i+d] <= heights[i]:\n",
    "                    if heights[i+d] < heights[i]:best = i+d\n",
    "                    i += d\n",
    "                if best != k:\n",
    "                    heights[best] += 1\n",
    "                    break\n",
    "            else:\n",
    "                heights[k] += 1\n",
    "        return heights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pourWater(self, H, V, K):\n",
    "        for _ in range(V):\n",
    "            for d in (-1, 1):\n",
    "                i = best = K\n",
    "                while 0 <= i+d < len(H) and H[i+d] <= H[i]:\n",
    "                    if H[i+d] < H[i]: best = i+d\n",
    "                    i += d\n",
    "                if best != K:\n",
    "                    H[best] += 1\n",
    "                    break\n",
    "            else:\n",
    "                H[K] += 1\n",
    "        return H"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, heights: List[int], V: int, k: int) -> List[int]:\n",
    "        #有点麻烦的模拟\n",
    "        n=len(heights)\n",
    "        for _ in range(V):\n",
    "            cur=k\n",
    "            best=k\n",
    "            #先左后右\n",
    "            while cur>0 and heights[cur]>=heights[cur-1]:\n",
    "                if heights[cur-1]<heights[cur]:\n",
    "                    best=cur-1\n",
    "                cur-=1\n",
    "            if best!=k:\n",
    "                heights[best]+=1\n",
    "                continue\n",
    "            while cur+1<n and heights[cur]>=heights[cur+1]:\n",
    "                if heights[cur+1]<heights[cur]:\n",
    "                    best=cur+1\n",
    "                cur+=1\n",
    "            if best!=k:\n",
    "                heights[best]+=1\n",
    "                continue\n",
    "            heights[k]+=1\n",
    "        return heights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, h: List[int], v: int, k: int) -> List[int]:\n",
    "        n = len(h)\n",
    "        while v:\n",
    "            st = k\n",
    "            while st > 0 and h[st-1] <= h[st]:\n",
    "                st -= 1\n",
    "            while st < k and h[st] == h[st+1]:\n",
    "                st += 1\n",
    "            if st != k:\n",
    "                h[st] += 1\n",
    "                v -= 1\n",
    "                continue\n",
    "            while st + 1 < n and h[st] >= h[st+1]:\n",
    "                st += 1\n",
    "            while st > k and h[st-1] == h[st]:\n",
    "                st -= 1\n",
    "            if st != k:\n",
    "                h[st] += 1\n",
    "                v -= 1\n",
    "                continue\n",
    "            h[k] += 1\n",
    "            v -= 1\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:\n",
    "        n = len(heights)\n",
    "        for _ in range(volume):\n",
    "            i = k \n",
    "            for j in range(k-1, -1, -1):\n",
    "                if heights[j] > heights[j+1]:\n",
    "                    break \n",
    "                if heights[j] < heights[i]:\n",
    "                    i = j \n",
    "            if heights[i] < heights[k]:\n",
    "                heights[i]+=1\n",
    "                continue \n",
    "            i = k \n",
    "            for j in range(k+1, n):\n",
    "                if heights[j] > heights[j-1]:\n",
    "                    break \n",
    "                if heights[j] < heights[i]:\n",
    "                    i = j \n",
    "            if heights[i] < heights[k]:\n",
    "                heights[i]+=1\n",
    "                continue \n",
    "            heights[k] += 1\n",
    "        return heights \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:\n",
    "        \n",
    "        n=len(heights)\n",
    "        v=volume\n",
    "        i=0\n",
    "        while v>0:\n",
    "            print(heights)\n",
    "            x=k-1\n",
    "            f=0\n",
    "            mi=heights[k]\n",
    "            while x>=0 and heights[x]<=heights[k]:\n",
    "                if heights[x]<heights[x+1]:\n",
    "                    i=x\n",
    "                    f=1\n",
    "                elif heights[x]>heights[x+1]:\n",
    "                    break\n",
    "                x=x-1\n",
    "            if f==1:\n",
    "                heights[i]+=1\n",
    "                v-=1\n",
    "                continue\n",
    "            x=k+1\n",
    "            while x<n and heights[k]>=heights[x]:\n",
    "                if heights[x]<heights[x-1]:\n",
    "                   # mi=heights[x]\n",
    "                    i=x\n",
    "                    f=1\n",
    "                elif heights[x]>heights[x-1]:\n",
    "                    break\n",
    "                x=x+1\n",
    "            if f==1:\n",
    "                heights[i]+=1\n",
    "                v-=1\n",
    "                continue\n",
    "            heights[k]+=1\n",
    "            v=v-1\n",
    "        return heights\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
